/**
 * Copyright (C) 2002 Michael Green <mtgreen@cs.ucsd.edu>
 * 
 * Copyright (C) 2002 Paul Kube <kube@cs.ucsd.edu>
 * 
 * Copyright (C) 2005 Owen Astrachan <ola@cs.duke.edu>
 * 
 * Copyright (C) 2011 Hoa Long Tam <hoalong.tam@berkeley.edu> and Armin Samii <samii@berkeley.edu>
 * 
 * This file is part of CS Boggle.
 * 
 * CS Boggle is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.
 * 
 * CS Boggle is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License along with CS boggle. If not, see <http://www.gnu.org/licenses/>.
 */

public class AutoPlayerBoardFirst extends AbstractPlayer
{
	public AutoPlayerBoardFirst(LexiconInterface lex)
	{
		this.initialize(lex);
	}

	/**
	 * Find all the valid words automatically, found words should be added via the <code>AbstractPlayer</code>'s <code>add</code> method.
	 * 
	 * @param board
	 *            is the BoggleBoard on which words are found
	 * @param lex
	 *            is the lexicon in which words are searched/validated
	 * @param minLength
	 *            of words found by an autoplayer
	 */
	public void findAllValidWords(BoggleBoard board, LexiconInterface lex, int minLength)
	{
		boolean visited[][];
		String search;

		for (int y = 0; y != board.size(); y++)
		{
			for (int x = 0; x != board.size(); x++)
			{
				search = "";
				visited = new boolean[board.size()][board.size()];
				findWord(x, y, board, visited, search);
			}
		}
	}

	/**
	 * Test function to make certain that the lexicon was loaded
	 */
	public boolean hasLexicon()
	{
		if (myLexicon != null)
		{
			return true;
		} else
		{
			return false;
		}
	}

	@Override
	public String getName()
	{
		return "AutoPlayer";
	}

	/**
	 * Finder function that traverses the board and checks if the word is in the dictionary. The finder will only move to an adjacent cell if the cell is unvisited, within the bounds of the board, and whose value concatenated with the searched string is a prefix (or word) in the dictionary.
	 * 
	 * When an adjacent cell meets these conditions, this function is called recursively using that cell such that the search word becomes a combination of the search word in the previous call concatenated with the value of the cell in the next call.
	 * 
	 * @param x
	 *            The column of the cell whose value is added to the end of the search string
	 * @param y
	 *            The row of the cell whose value is added to the end of the search string
	 * @param board
	 *            The board model of the game. We search this board for words that are in the lexicon
	 * @param visited
	 *            A 2D boolean array of visited cells. True means that the cell has been visited
	 * @param search
	 *            The word we search for in the lexicon. If the word is in the lexicon, it is added to the words of the player
	 */
	private void findWord(int x, int y, BoggleBoard board, boolean[][] visited, String search)
	{
		search += board.getFace(x, y).charAt(0) == 'q' ? "qu" : board.getFace(x, y);
		visited[x][y] = true;

		if (myLexicon.contains(search))
		{
			add(search);
		}

		for (int j = -1; j != 2; j++)
		{
			for (int i = -1; i != 2; i++)
			{
				// If cell is not current cell and is in bounds, not already
				// visited, and whose value concatenated with the search word is
				// a prefix or word in the dictionary
				if ((i != 0 || j != 0) && board.isInBounds(x + i, y + j) && !visited[x + i][y + j])
				{
					String newSearch = search + (board.getFace(x + i, y + j).charAt(0) == 'q' ? "qu" : board.getFace(x + i, y + j).charAt(0));
					if (myLexicon.containsPrefix(newSearch) || myLexicon.contains(newSearch))
					{
						findWord(x + i, y + j, board, visited, search);
					}
				}

			}
		}

		visited[x][y] = false;
		search = search.substring(0, search.length() - 1);
	}
}